#include <iostream>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
//二叉搜索树的中序遍历为排好序的序列
class Solution {
public:
    int index;
    TreeNode* ans;
    void helper(TreeNode* p,int k){
        
        if(p==nullptr){
            return ;
        }
        helper(p->left,k);
        index++;
        //cout << p->val<<endl;
        if(index==k){
            ans=p;
        }
        helper(p->right,k);
    }
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        index=0;
        ans=nullptr;
        helper(pRoot,k);
        return ans;
    }    
};
TreeNode* h(){
    TreeNode* p=new TreeNode(5);
    p->left=new TreeNode(3);
    p->right=new TreeNode(7);
    TreeNode* q=p->left;
    q->left=new TreeNode(2);
    q->right=new TreeNode(4);
    q=p->right;
    q->left=new TreeNode(6);
    q->right=new TreeNode(8);
    return p;
}
int main(){
    TreeNode* p=h();
    Solution s;
    TreeNode *ans=s.KthNode(p,3);
    cout << "ans : "<< ans->val<<endl;
    return 0;
}